The present invention generally relates to a packet switching method and apparatus in which information of a forwarding packet is used in routing, and particularly to a packet switching method and apparatus suitable for multicast communications.
The term xe2x80x9cmulticast communicationsxe2x80x9d means that a packet addressed to a multicast group from one computer (node) is relayed and transmitted to a plurality of computers (nodes) belonging to the group. FIG. 1 is a diagram showing the concept of the multicast communications. As illustrated, a packet from a computer 150 of source S is relayed and transmitted through routers (packet switching devices) R1-R9 to all computers 151-157 associated with the same group G. Here, the group is the communication unit of the multicast communications. The router holds a plurality of relay interfaces for one group. Fundamentally, in the multicast communications, the same packet is not relayed to the same computer and router. Therefore, the receiving interface of a router is always a 1-interface. However, the above fact is not true for the route solution stage in the routing protocol.
In the multicast communications shown in FIG. 1, each router received a packet addressed to a multicast group does not relay the packet to a link 158 between the routers R1 and R4, a link 159 between the routers R4 and R3, a link 160 between the routers R2 and R3, a link 161 between the routers R6 and R9, and a link 162 between the routers R8 and R9 all of which are the redundant routes of the multicast communications. In addition, when the source side of data is referred to as an upstream side and the destination side of data is referred to as a downstream side, the router R7, for example, does not need to relay the packet to a path 163 on the upstream side since the router R2 located on the upstream side relays the packet to the computer 151 connected to the router R2, but it may relay the packet only to links 164 and 165 on the downstream side.
FIG. 2 is a diagram showing one example of a network system for the IP (Internet Protocol) multicast communications. Routers R1-R6 are routers for IP multicast. That is, the routers R1-R6 are packet repeaters for relaying IP datagram which is a communication unit packet of IP protocol. Computers 126-134 of sources S1-S9 are computers for IP multicast protocol, and are sending and receiving terminals of the IP datagram. Groups G1-G3 indicate the ranges of the IP multicast communications.
In this network system, the computes 126, 128 and 134 of sources S1, S3 and S9 belong to the group G1, the computers 128, 129, 133 and 134 of sources S3, S4, S8 and S9 to the group G2, and the computes 127, 130, 131, 132 and 133 of sources S2, S5, S6, S7 and S8 to the group G3. Therefore, the IP datagram transmitted to the group G1 is relayed to the computers 126, 128 and 134 of sources S1, S3 and S9, the IP data gram transmitted to the group G2 is relayed to the computers 128, 129, 133 and 134 of sources S3, S4, S8 and S9, and the IP datagram transmitted to the group G3 is relayed to the computers 127, 130, 131, 132 and 133 of sources S2, S5, S6, S7 and S8. The router R1 at the center of the diagram has an interface xe2x80x9caxe2x80x9d connected to the router R2, an interface xe2x80x9cbxe2x80x9d connected to the router R6, an interface xe2x80x9ccxe2x80x9d connected to the router R4, an interface xe2x80x9cdxe2x80x9d connected to the computer 128 of source S3, an interface xe2x80x9cexe2x80x9d connected to the computer 129 of source S4, and an interface xe2x80x9cfxe2x80x9d connected to the router R5.
The multicast communications routing system includes a system in which the user previously sets the multicast communication routing information in each router, and a system in which the multicast communications routing information is transmitted and received between the routers according to the routing protocol to automatically calculate a multicast communications route. Here, as the multicast routing protocol, there are a routing protocol X and a routing protocol Y which will be described below. The routing protocol X is the routing protocol of the broadcast and prune system, and there is DVMRP (RFC1075) as a typical example. The routing protocol Y is the routing protocol of the explicit join system, and there is PIM-SM (RFC2117) as a typical example.
FIGS. 3A and 3B are diagrams for explaining the operation of the routing protocol X. According to the routing protocol X, when a router R10 receives IP datagram 170 from a computer 176 of source S1, it relays the IP datagram 170 to routers R20, R30, R40 on the downstream side (see IP datagram 171-173). The router R20 received the IP datagram 171 relays it to a computer 177 since the router R20 is connected to the computer 177 belonging to the destination group G1 of the IP datagram 171. The router R30 received the IP datagram 172 also repays it to a computer 178 since the router R30 is connected to the computer 178 belonging to the destination group G1 of the IP datagram 172. However, the router R40 received the IP datagram 173 transmits a prune request 175, which rejecting the relaying of IP datagram of the source address S1 and the destination group G1, to the router R10 which relayed the IP datagram 173, since the connected computer 179 does not belong to the destination group G1 of the IP datagram 173. Then, as shown in FIG. 3B, the IP router R10 received the prune request 175 receives IP datagram 180 having the rejected source address S1 and destination group G1, but does not relay the IP datagram 180 to the router R40 which transmitted the prune request 175.
FIGS. 4A and 4B are diagrams for explaining the operation of the routing protocol Y. According to the routing protocol Y, as illustrated in FIG. 4A, computers 190 and 191 which desire to relay IP datagram of a destination group G1 issue join requests 194 and 195, which include a group information (G1), to routers R21 and R31 on the upstream side, respectively. The routers R21 and R31 register interfaces 204 and 205 which received the join requests 194 and 195, and the group information (G1) included in the join requests 194 and 197. Also, the routers R21 and R31 issue the join requests 196 and 197, which include the group information (G1), to the router R11 on the upstream side. The router R11 registers interfaces 201 and 202 which received the join requests 196 and 197, and the group information (G1) included in the join requests 196 and 197. Then, as shown in FIG. 4B, when the router R11 receives IP datagram 200 of the destination group G1 coincident with the registered group information (G1) from the computer 193 of source S, it relays the IP datagram 200 only to the routers R21 and R31 connected to the interfaces 201 and 202 which received the join requests 196 and 197. The routers R21 and R31 operate as does the router R11. Thus, the IP datagram 200 is transmitted to the computers 190 and 191 which issued the join requests 194 and 195, but is not transmitted to the computer 192 which did not issue the joint request.
FIG. 5 is a diagram showing one example of the header format of IP datagram. In the multicast communications, a source address (SX) is stored in a source address field 210 of the IP datagram header, and a multicast destination group address (GX) is stored in a destination address field 211 of the IP datagram header. The destination group address (GX) is of class D in order to coexist with or be distinguished from the existing IP destination address (of classes A-C). FIG. 6 shows the class-D address format. The first four bits xe2x80x9c1110xe2x80x9d in FIG. 6 means the class D. By the way, the class A is indicated by the first one bit of xe2x80x9c0xe2x80x9d, the class B by the second two bits of xe2x80x9c10xe2x80x9d, and the class C by the first three bits of xe2x80x9c110xe2x80x9d.
A conventional packet switching apparatus capable of being used as the router R1 in the multicast network system shown in FIG. 2 will be described with reference to FIGS. 7-9.
FIG. 7 is a block diagram of a packet switching apparatus in which a forwarding unit 235 and a routing unit 236 shown in FIG. 9 are constructed by using separate processors 245 and 246. In this packet switching apparatus, the routing unit 236 includes the processor 245 and a memory 240, and the forwarding unit 235 includes the processor 246, a memory 241, a comparator 243 and six interfaces xe2x80x9caxe2x80x9d-xe2x80x9cfxe2x80x9d. Here, the comparator 243 compares the contents of a table stored in the memory 241 with a specified pattern. If the processor 246 is adapted to execute the function of the comparator 243, the comparator 243 can be omitted. In addition, the processors 245 and 246 may be constructed to execute the programs stored in the memories 240 and 241 or to operate according to hardware logic.
FIG. 8 is a block diagram of a packet switching apparatus in which the forwarding unit 235 and routing unit 236 shown in FIG. 9 are constructed by using the same processor 247. In this packet switching apparatus, the routing unit 236 and the forwarding unit 235 include the processor 247, a memory 242, a comparator 244 and six interfaces xe2x80x9caxe2x80x9d-xe2x80x9cfxe2x80x9d. Here, the comparator 244 compares the contents of a table stored in the memory 242 with a specified pattern. If the processor 247 is adapted to execute the function of the comparator 244, the comparator 244 can be omitted. In addition, the processor 247 may be constructed to execute the program stored in the memory 242 or to operate according to hardware logic.
The switching system concept of the conventional packet switching apparatus capable of being used as the router R1 in the multicast network system shown in FIG. 2 will be described with reference to FIG. 9.
The packet switching apparatus (router R1) has one or more physical or logic interfaces (interfaces xe2x80x9caxe2x80x9d-xe2x80x9cfxe2x80x9d), and can be divided roughly into two blocks, or the forwarding unit 235 and the routing unit 236.
The forwarding unit 235 has a routing information table 234 for routing a particular packet. The forwarding unit 235 compares the address information (source address S1 and destination group address G1) of a packet 227 received from one interface xe2x80x9caxe2x80x9d with the contents of the address section of the routing information table 234. If both are coincident at an entry on the routing information table 234, the switching operation is performed according to the contents of the corresponding outgoing interface (OUT i/f) section of the entry. On the routing information table 234, there is registered the results (information composed of the address section, receiving interface (IN i/f) section and outgoing interface section) of the received packet rout-calculated by the routing unit 236. The routing information table 234 is stored in the memory 241 of the hardware construction shown in FIG. 7, or in the memory 242 of the hardware construction shown in FIG. 8. In addition, the address information of the received packet 227 is compared with the contents of the address section of the routing information table 234 by the comparator 243 of the hardware structure shown in FIG. 7 or by the comparator 244 of the hardware construction shown in FIG. 8.
The routing unit 236 has a parts-of-routing-information table 220 which includes a source information 240 for confirming whether or not the source information is received from a correct interface and a destination information 241 indicating a relayed terminal with the destination. In the receiving interface section of the source information 240, the interfaces most suitable for the source registered in the source section are registered. The group addresses are registered in the address group section of the destination information 241 on the parts-of-routing-information table 220, and a plurality of interfaces most suitable for relaying to the destination groups are registered in the outgoing interface section thereof. The parts-of-routing-information table 220 is sometimes set by the user or between the apparatuses by the routing protocol or the like as described above. The parts-of-routing-information table 220 is stored in the memory 240 of the hardware structure shown in FIG. 7, or in the memory 242 of the hardware construction shown in FIG. 8.
In the packet switching apparatus of this structure, when the forwarding unit 235 receives through the interface xe2x80x9caxe2x80x9d a packet 232 which has an address information (source address S1 and destination group address G1) not registered in the routing information table 234, the received packet 232 is registered in a routing queue 237. Thereafter, the forwarding unit 235 supplies to the routing unit 236 a no-matching-information of destination address 233 which is composed of the address information (source address S1 and destination group address G1) of the received packet 232 and the receiving interface information (interface xe2x80x9caxe2x80x9d).
When the routing unit 236 receives the no-matching-information of destination address 233 from the forwarding unit 235, it calculates the confirmation of the reception route correction and the destination on the basis of the no-matching-information of destination address 233. Specifically, the destination group address G1 included in the no-matching-information of destination address 233 and the destination information 241 of the parts-of-routing-information table 220 are compared for each entry. If the content of the destination group section is coincident with the destination group address G1, the interfaces xe2x80x9caxe2x80x9d, xe2x80x9cbxe2x80x9d, xe2x80x9ccxe2x80x9d, xe2x80x9cdxe2x80x9d and xe2x80x9cfxe2x80x9d registered in the outgoing interface section at the corresponding entry (the top entry as illustrated) are taken out. Then, the source address S1 included in the no-matching-information of destination address 233 is compared with the contents of the source information 240 of the parts-of-routing-information table 220 for each entry. If the content of the source section coincides with the source address S1, the interface xe2x80x9caxe2x80x9d registered in the receiving interface section at the corresponding entry (the top entry as illustrated) is taken out. Thereafter, of the interfaces xe2x80x9caxe2x80x9d, xe2x80x9cbxe2x80x9d, xe2x80x9ccxe2x80x9d, xe2x80x9cdxe2x80x9d and xe2x80x9cfxe2x80x9d taken out from the destination information 241, the interface xe2x80x9caxe2x80x9d taken out from the source information 240 is deleted to produce a routing information entry additional request 238. The routing information entry additional request 238 is sent from the routing unit 236 to the forwarding unit 235.
The forwarding unit 235 stores the received routing information entry additional request 238 in the routing information table 234. In addition, the forwarding unit 235 relays the packet, which has the source address and destination group address coincident with the address section 239 (source address S1 and destination group address G1) of the routing information entry additional request 238, of the packets registered in the routing queue 237 to the interfaces xe2x80x9cbxe2x80x9d, xe2x80x9ccxe2x80x9d, xe2x80x9cdxe2x80x9d and xe2x80x9cfxe2x80x9d according to the contents of the outgoing interface section of the routing information entry additional request 238 (see packets 228-231). Then, when the packet having the same source address and destination group address arrives, the forwarding unit 235 relays the packet according to the routing information table 234 added the routing information entry additional request 238.
If a new routing information cannot be produced while the routing unit 236 is calculating a route on the basis of the no-matching-information of destination address 233 received from the forwarding unit 235, the routing unit 236 sends information of being not able to produce a routing information (not shown) to the forwarding unit 235. When the forwarding unit 235 receives this information, it deletes the packet specified by the information from the routing queue 237.
Although not shown, the routing unit 236 manages the routing information table 234 of the forwarding unit 235, and orders the forwarding unit 235 to update the routing information table 234 according to the status change in the network or the like.
In the packet switching apparatus shown in FIG. 9, when a packet the destination of which is not registered in the routing information table of the forwarding unit is received, the forwarding unit registers the received packet in the routing queue, and then reports the no-matching-information of destination address to the routing unit. Thereafter, the forwarding unit waits for a new routing information or information of being not able to produce a routing information from the routing unit, and relays or deletes the received packet. As a result, there is a problem that the transmission delay occurs in the relaying of packet. In addition, there is a problem that the overflow is caused at the time of congestion because the routing queue is limited, so that the packet to be relayed is discarded. When the routing unit receives the no-matching-information of destination address from the forwarding unit, it calculates a route one by one. Consequently, when a new routing information cannot be produced, there is a problem that the routing unit makes the redundant calculation of route for the packet which cannot be relayed originally.
It is an object of the present invention to provide a packet switching method and apparatus capable of preventing from or reducing the generation of the transmission delay of the forwarding packet because the forwarding unit waits for distribution of a routing information from the routing unit, the throwing away of packet due to the overflow in the routing queue and the redundant calculation of route in the routing unit for the packet that cannot be repeated originally.
In order to achieve the above object, according to the present invention, the order of processing of route calculation and packet relaying is changed, so that the relaying route is determined on the basis of a parts-of-route-information before the route calculation. Then, after relaying the packet, the route calculation is performed to produce a routing information. The succeeding packets of the same source and destination are transmitted according to the produced routing information.
The routing unit previously distributes to the forwarding unit a parts-of-route-information set by the user or a parts-of-route-information produced on the basis of a route information collected by the communications between the neighboring packet switching apparatuses or between computers. When the forwarding unit receives a packet the destination of which does not exist in the routing information, it utilizes the parts-of-route-information previously distributed from the routing unit to calculate a route, and sends or discards the packet without storing in the routing queue. At the same time, the forwarding unit reports to the routing unit a no-matching-information of destination address that includes the received packet information the destination address of which does not exist in the routing information. The routing unit regularly produces a new routing information on the basis of the kept parts-of-route-information, and the received packet information of the no-matching-information of destination address from the forwarding unit, and distributes it to the forwarding unit. The next incoming packet of the same destination is relayed by the forwarding unit according to the routing information distributed from the routing unit.
Thus, when a packet the destination of which is not registered in the routing information is received, there are no delay of packet transmission due to the route calculation and no discard of packet due to the overflow in the routing queue. In addition, since the packet which cannot be relayed is discarded in the forwarding unit, the no-matching-information of destination address is not needed to report to the routing unit, and thus the redundant processing in the routing unit can be prevented from occurring.
Since the forwarding unit reports the no-matching-information of destination address to the routing unit and the routing unit regularly produces the routing information and distributes it to the forwarding unit, it is sure that the routing information managed by the routing unit coincides with that of the forwarding unit.